package busquedasciegas;

import java.util.ArrayList;
import java.util.TreeMap;

import busquedasciegas.EstadoPuzzle.Key;


/**
 * Implementación del algoritmo Primero en Anchura (o Amplitud).
 * @author german
 *
 */
public class PrimeroAnchura{
	
	ArrayList<Key> cola;
	TreeMap<Key, EstadoPuzzle> arbol;
	
	public PrimeroAnchura(int cuadrados){
		cola = new ArrayList<Key>();
		arbol = new TreeMap<Key, EstadoPuzzle>();
	}
	
	/**
	 * Busca en un espacio de búsqueda el estado objetivo o meta
	 * haciendo un recorrido primero en anchura.
	 * @param inicial Representación del estado inicial.
	 * @param meta Representación del estado final.
	 */
	public String buscar(EstadoPuzzle inicial, int[] meta){
		
		EstadoPuzzle actual;		
		String traza = "";
		ArrayList<EstadoPuzzle> hijos = new ArrayList<EstadoPuzzle>();
		cola.add(inicial.key);
		arbol.put(inicial.key, inicial);
		arbol.get(inicial.key).visitado = true;
		
		while (!cola.isEmpty()){
			
			actual = arbol.get(cola.get(0));
			cola.remove(0);
			hijos = actual.generarDescendientes();
			
			for (EstadoPuzzle hijo : hijos) {
				if ((!arbol.containsKey((hijo.key))) && (!hijo.isVisitado())){
					arbol.put(hijo.key, hijo);
					cola.add(hijo.key);
				}

				if ((!hijo.isVisitado()) && (!iguales(hijo.key.tablero, meta))){
					hijo.setVisitado(true);
				}
				else{
					if (iguales(hijo.key.tablero, meta)){
						traza = hallarTraza(inicial, hijo);
						return traza;
					}
				}
			}
		}
		return traza;
	}
	
	/**
	 * Busca en la estructura árbol construida en la función Buscar
	 * el camino o traza que lleva del estado inicial al estado final.
	 * @param raiz Representación del estado inicial.
	 * @param meta Representación del estado final, meta u
	 * objetivo.
	 */
	public String hallarTraza(EstadoPuzzle raiz, EstadoPuzzle meta){
		
		String oper = "";
		EstadoPuzzle actual = arbol.get(meta.key);
		
		ArrayList<EstadoPuzzle> sol = new ArrayList<EstadoPuzzle>();
		while (actual != null){
			sol.add(actual);
			actual = actual.padre;
		}
		oper = oper + "Solucion: " + "\n";
		int numMov = sol.size();
		for(int i = 0; i < numMov; i++){
			oper = oper + sol.get(sol.size()-1) + "\n";
			sol.remove(sol.size()-1);
		}
		return oper;
	}
	
	/**
	 * 
	 * @param a Matriz que representa el tablero del puzzle.
	 * @param b Matriz que representa el tablero del puzzle.
	 * @return Retorna true si las matrices a y b son iguales,
	 * es decir, tienen los mismos elementos.
	 */
	private boolean iguales(int[] a, int[] b)
	{
		for (int i = 0; i < a.length; i++){
			if (a[i] != b[i]){
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		PrimeroAnchura pa = new PrimeroAnchura(9);
		ArrayList<Integer> inicial = new ArrayList<Integer>();
		int[] meta = new int[9];
		meta[0] = 1;
		meta[1] = 2;
		meta[2] = 4;
		//meta[0][3] = 5;
		meta[3] = 8;
		meta[4] = 0;
		meta[5] = 3;
		//meta[1][3] = 8;
		meta[6] = 7;
		meta[7] = 6;
		meta[8] = 5;
		//meta[2][3] = 11;
//		meta[3][0] = 13;
//		meta[3][1] = 14;
//		meta[3][2] = 15;
		//meta[3][3] = 12;
		inicial.add(2);
		inicial.add(8);
		inicial.add(3);
		inicial.add(1);
		inicial.add(6);
		inicial.add(4);
		inicial.add(7);
		inicial.add(0);
		inicial.add(5);
//		inicial.add(10);
//		inicial.add(11);
//		inicial.add(12);
//		inicial.add(13);
//		inicial.add(14);
//		inicial.add(15);
//		inicial.add(0);
		EstadoPuzzle e = new EstadoPuzzle(inicial);
		System.out.println(pa.buscar(e, meta));
	}

	
}
